// #include <iostream>
// using namespace std;

// int main()
// {
//     int a = 10;
//     int b = 20;
    
//     cout << "Hello C++" << endl;
//     return 0;
// }


#define _CRT_SECURE_NO_WARNINGS 1

#include"ThreadCache.h"
#include"CentralCache.h"

//从中心缓存获取对象
void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
{
	// 慢开始反馈调节算法
	// 1. 最开始不会一次向central cache要太多, 因为可能用不完
	// 2. 如果你不断有这个size大小的内存需求, 那么batchNum就会不断增长, 直至上限
	// 3. size越大,一次向central cache要的batchNum就越小
	// 4. size越小,一次向central cache要的batchNum就越大
	size_t batchNum = std::min(_freeLists[index].MaxSize(), SizeClass::NumMoveSize(size));
	if (_freeLists[index].MaxSize() == batchNum)
		_freeLists[index].MaxSize() += 1;

	void* start = nullptr;
	void* end = nullptr;
	size_t actualNum = CentralCache::GetInstance()->FetchRangeObj(start, end, batchNum, size);
	assert(actualNum > 0);

	if (actualNum == 1)
	{
		assert(start == end);
		return start;
	}
	else
	{
		_freeLists[index].PushRange(NextObj(start), end); 
		return start;
	}
}

// 申请和释放内存对象
void* ThreadCache::Allocate(size_t size)
{
	assert(size <= MAX_BYTES);

	size_t alignSize = SizeClass::RoundUp(size);
	size_t index = SizeClass::Index(size);

	if (!_freeLists[index].Empty())
	{
		return _freeLists[index].Pop();
	}
	else
	{
		return FetchFromCentralCache(index, alignSize);
	}
}

void ThreadCache::Deallocate(void* ptr, size_t size)
{
	assert(ptr);
	assert(size <= MAX_BYTES);

	// 找到对应的自由链表桶, 头插进去
	size_t index = SizeClass::Index(size);
	_freeLists[index].Push(ptr);

	// ...
}


#define _CRT_SECURE_NO_WARNINGS 1

#include"CentralCache.h"

CentralCache CentralCache::_sInst;


// 从SpanList或者page cache获取一个非空的Span
Span* CentralCache::GetOneSpan(SpanList& list, size_t byte_size)
{
	// ...

	return nullptr;
}

// 从中心缓存获取一定数量的对象给thread cache
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t byte_size)
{
	size_t index = SizeClass::Index(byte_size);

	_spanList[index]._mtx.lock();

	Span* span = GetOneSpan(_spanList[index], byte_size);
	assert(span);
	assert(span->_freeList);

	// 从span中获取batchNum个内存对象
	// 如果不够batchNum个, 有多少拿多少
	start = span->_freeList;
	end = start;
	size_t i = 0;
	size_t actualNum = 1;
	while (i < batchNum - 1 && NextObj(end) != nullptr)
	{
		end = NextObj(end);
		i++;
		actualNum++;
	}
	span->_freeList = NextObj(end);
	NextObj(end) = nullptr; // 这个操作什么意思   取出的一段链表的表尾置空

	_spanList[index]._mtx.unlock();

	return actualNum;
}





#define _CRT_SECURE_NO_WARNINGS 1

#include"CentralCache.h"
#include"PageCache.h"

CentralCache CentralCache::_sInst;


//// 从SpanList或者page cache获取一个非空的Span
//Span* CentralCache::GetOneSpan(SpanList& list, size_t byte_size)
//{
//	// 先查看当前的SpanList中是否还有未分配的span
//	Span* it = list.Begin();
//	while (it != list.end())
//	{
//		if (it->_freeList != nullptr)
//		{
//			return it;
//		}
//		else
//		{
//			it = it->_next;
//		}
//	}
//
//	// 先把central cache的桶锁解掉, 这样如果其他线程释放内存对象回来不会阻塞
//	list._mtx.unlock();
//
//	// 走到这说明当前的SpanList中没有未分配的span, 需要从page cache中获取
//	PageCache::GetInstance()->_pageMtx.lock();
//	Span* span = PageCache::GetInstance()->NewSpan(SizeClass::NumMovePage(byte_size));
//	PageCache::GetInstance()->_pageMtx.unlock();
//
//	// 对获取的span进行切分不需要加锁, 因为这会其他线程获取不到这个span
//
//	// 计算span大块内存的起始地址和大块内存的大小
//	char* start = (char*)(span->_pageId << PAGE_SHIFT); // 大块内存的起始地址
//	size_t bytes = span->_n << PAGE_SHIFT; // 大块内存的大小 - 字节数
//	char* end = start + bytes; // 大块内存的结束地址
//
//	// 把大块内存切成自由链表链接起来
//	// 1. 先切下来一块做头, 方便尾插 - 提高命中率
//	span->_freeList = start;
//	start += byte_size;
//	void* tail = span->_freeList;
//	int i = 1;
//	while (start < end)
//	{
//		++i;
//		NextObj(tail) = start;
//		tail = NextObj(tail); // tail = start;
//		start += byte_size;
//	}
//
//	// 切好span以后，需要把span挂到桶里面去的时候，再加锁
//	list._mtx.lock();
//	list.PushFront(span);
//
//	return span;
//}


// 从SpanList或者page cache获取一个非空的span
Span* CentralCache::GetOneSpan(SpanList& list, size_t byte_size)
{
	// 先查看当前的SpanList中是否还有未分配的span
	Span* it = list.Begin();
	while (it != list.end())
	{
		if (it->_freeList != nullptr)
		{
			return it;
		}
		else
		{
			it = it->_next;
		}
	}

	// 先把central cache的桶锁解掉, 这样如果其他线程释放内存回来不会被阻塞
	list._mtx.unlock();

	// 走到这里说明当前的SpanList中没有未分配的span, 需要从page cache中获取
	PageCache::GetInstance()->_pageMtx.lock();
	Span* span = PageCache::GetInstance()->NewSpan(SizeClass::NumMovePage(byte_size));
	PageCache::GetInstance()->_pageMtx.unlock();

	// 对获取的span进行切分不需要加锁, 因为这会其他线程获取不到这个span

	// 计算span大块内存的起始地址和大块内存的大小
	char* start = (char*)(span->_pageId << PAGE_SHIFT); // 大块内存的起始地址
	size_t bytes = span->_n << PAGE_SHIFT; // 大块内存的大小 - 字节数
	char* end = start + bytes; // 大块内存的结束地址

	// 把大块内存切成自由链表链接起来
	// 先切下一块做头, 方便尾插 - 提高效率
	span->_freeList = start;
	start += byte_size;
	void* tail = span->_freeList;
	size_t i = 1;
	while (start < end)
	{
		NextObj(tail) = start;
		tail = start;
		start += byte_size;
		i++; // 这个i有什么用呢?
	}

	// 切好span以后, 需要将span挂到桶里面去, 再加锁
	list._mtx.lock();
	list.PushFront(span);

	return span;
}

// 从中心缓存获取一定数量的对象给thread cache
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t byte_size)
{
	size_t index = SizeClass::Index(byte_size);

	_spanList[index]._mtx.lock();

	Span* span = GetOneSpan(_spanList[index], byte_size);
	assert(span);
	assert(span->_freeList);

	// 从span中获取batchNum个内存对象
	// 如果不够batchNum个, 有多少拿多少
	start = span->_freeList;
	end = start;
	size_t i = 0;
	size_t actualNum = 1;
	while (i < batchNum - 1 && NextObj(end) != nullptr)
	{
		end = NextObj(end);
		i++;
		actualNum++;
	}
	span->_freeList = NextObj(end);
	NextObj(end) = nullptr; // 这个操作什么意思   取出的一段链表的表尾置空

	_spanList[index]._mtx.unlock();

	return actualNum;
}

#pragma once


#include<iostream>
#include<cassert>
#include<algorithm>
#include<mutex>
using std::cout;
using std::endl;


static const size_t NFREELISTS = 208;
static const size_t MAX_SIZE = 256 * 1024;
static const size_t PAGE_SHIFT = 13;


// 获取内存对象存储的头4/8个字节的值, 即链接的下一个对象的地址
inline void*& NextObj(void* ptr)
{
	return (*(void**)ptr);
}


class FreeList
{
public:
	void PushRange(void* start, void* end)
	{
		assert(start);
		assert(end);

		NextObj(end) = _freeList;
		_freeList = start;
	}

	// 头插
	void Push(void* obj)
	{
		assert(obj);

		NextObj(obj) = _freeList;
		_freeList = obj;
	}

	// 头删
	void* Pop()
	{
		assert(_freeList);

		void* obj = _freeList;
		_freeList = NextObj(_freeList);

		return obj;
	}

	// 判空
	bool Empty()
	{
		return _freeList == nullptr;
	}

	size_t& MaxSize()
	{
		return _maxSize;
	}

private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;
};


// 对齐映射规则
class SizeClass 
{
public:
	// 整体控制在最多10%左右的内碎片浪费
	// [1, 128]                          8byte对齐                          freeList[0, 16)
	// [128+1, 1024]                     16byte对齐                         freeList[16, 72)
	// [1024+1, 8*1024]                  128byte对齐                        freeList[72, 128)
	// [8*1024+1, 64*1024]               1024byte对齐                       freeList[128, 184)
	// [64*1024+1, 256*1024]             8*1024byte对齐                     freeList[184, 208)


	// 对齐大小的计算 - 对齐后给的字节数
	/*static inline size_t _RoundUp(size_t size, size_t alignNum)
	{
		size_t alignSize = 0;
		if (size % alignNum != 0)
		{
			alignSize = (size / alignNum + 1) * alignNum;
		}
		else
		{
			alignSize = size;
		}

		return alignSize;
	}*/

	static inline size_t _RoundUp(size_t size, size_t alignNum)
	{
		return ((size + alignNum - 1) & ~(alignNum - 1));
	}

	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			assert(false);
		}
		return -1;
	}


	//计算映射到哪一个自由链表桶
	/*static inline size_t _Index(size_t bytes, size_t alignNum)
	{
		if (bytes % alignNum == 0)
		{
			return bytes / alignNum - 1;
		}
		else
		{
			return bytes / alignNum;
		}
	}*/

	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}

	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_SIZE);

		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };// 前四个区间桶的数量

		if (bytes <= 128)
		{
			// return _Index(bytes, 8);
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			// return _Index(bytes, 16) + group_array[0];
			return _Index(bytes, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024)
		{
			// return _Index(bytes, 128) + group_array[0] + group_array[1];
			return _Index(bytes, 7) + group_array[0] + group_array[1];
		}
		else if (bytes <= 64 * 1024)
		{
			// return _Index(bytes, 1024) + group_array[0] + group_array[1] + group_array[2];
			return _Index(bytes, 10) + group_array[0] + group_array[1] + group_array[2];
		}
		else if (bytes <= 256 * 1024)
		{
			// return _Index(bytes, 8 * 1024) + group_array[0] + group_array[1] + group_array[2] + group_array[3];
			return _Index(bytes, 13) + group_array[0] + group_array[1] + group_array[2] + group_array[3];
		}
		else
		{
			assert(false);
		}
		return -1;
	}

	// 一次批量向central cache申请多少个对象
	static size_t NumMoveSize(size_t size)
	{
		assert(size > 0);

		size_t num = MAX_SIZE / size;

		if (num < 2)
			num = 2;
		if (num > 512)
			num = 512;

		return num;
	}
};


#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#endif


// span是管理以页为单位的大块内存
struct Span
{
	PAGE_ID _pageId = 0; // 大块内存起始页的页号
	size_t _n = 0; // 页的数量

	Span* _prev = nullptr; // 双向链表结构
	Span* _next = nullptr;

	void* _freeList = nullptr; // 切好的小块内存的自由链表
};


class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_prev = _head;
		_head->_next = _head;
	}

	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		// prev newSpan pos
		prev->_next = newSpan;
		newSpan->_prev = prev;

		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	void* Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

private:
	Span* _head = nullptr;

public:
	std::mutex _mtx;
};


#pragma once


#include"Common.h"


//thread cache本质是一个哈希桶, 每个位置映射的是一个自由链表
class ThreadCache
{
public:
	// 申请内存对象
	void* Allocate(size_t size);

	// 从central cache中获取对象
	void* FetchFromCentralCache(size_t index, size_t size);


private:
	FreeList _freeLists[NFREELISTS];
};


// 线程通过TLS获取它独享的thread cache
// TLS thread local storage
static __declspec(thread) ThreadCache* pTLSThreadCache = nullptr;


#define _CRT_SECURE_NO_WARNINGS 1


#include"ThreadCache.h"
#include"CentralCache.h"


void* ThreadCache::Allocate(size_t size)
{
	assert(size <= MAX_SIZE);

	size_t alignSize = SizeClass::RoundUp(size);
	size_t index = SizeClass::Index(size);

	// 判断thread cache当前映射的自由链表是否为空
	if (!_freeLists[index].Empty())
	{
		return _freeLists[index].Pop();
	}
	else
	{
		return FetchFromCentralCache(index, alignSize);
	}
}


// 从中心缓存获取内存对象
void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
{
	// 慢开始反馈调节算法
	// 1. 最开始不会一次向central cache要太多, 因为可能用不完
	// 2. 如果你不断有这个size大小的内存需求, 那么这个batchNum就不会断增长, 直至上限
	// 3. size越小, 一次向central cache要的内存对象就越多
	// 4. size越大, 一次向central cache要的内存对象就越少
	size_t batchNum = std::min(_freeLists[index].MaxSize(), SizeClass::NumMoveSize(size));
	if (_freeLists[index].MaxSize() == batchNum)
		_freeLists[index].MaxSize() += 1;

	void* start = nullptr;
	void* end = nullptr;

	size_t actualNum = CentralCache::GetInstance()->FetchRangeObj(start, end, batchNum, size);
	assert(actualNum > 0);

	if (actualNum == 1)
	{
		assert(start == end);
		return start;
	}
	else
	{
		_freeLists[index].PushRange(NextObj(start), end);
		return start;
	}
}

#define _CRT_SECURE_NO_WARNINGS 1


#include"CentralCache.h"


// 从SpanList或者page cache获取一个非空的span
Span* CentralCache::GetOneSpan(SpanList& list, size_t byte_size)
{
	assert(byte_size <= MAX_SIZE);

	// ...
	return nullptr;
}


// 从中心缓存获取一定数量的内存对象给thread cache
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t byte_size)
{
	assert(byte_size <= MAX_SIZE);

	size_t index = SizeClass::Index(byte_size);

	_spanLists[index]._mtx.lock();

	// 获取一个非空的span
	Span* span = GetInstance()->GetOneSpan(_spanLists[index], byte_size);
	assert(span);
	assert(span->_freeList);

	span->_pageId <<

	// 将获取到的span切成对应大小的小块内存
	start = span->_freeList;
	end = start;
	size_t actualNum = 1;
	while (start < end)
	{

	}


	_spanLists[index]._mtx.unlock();
}

#define _CRT_SECURE_NO_WARNINGS 1


#include"CentralCache.h"
#include"PageCache.h"


//// 从SpanList或者page cache获取一个非空的span
//Span* CentralCache::GetOneSpan(SpanList& list, size_t byte_size)
//{
//	assert(byte_size <= MAX_SIZE);
//
//	// 先看当前的SpanList中有没有非空的span
//	Span* it = list.Begin();
//	while (it != list.End())
//	{
//		if (it->_freeList != nullptr)
//		{
//			return it;
//		}
//		else
//		{
//			it = it->_next;
//		}
//	}
//
//	// 解掉桶锁, 方便从thread cache释放回来内存
//	list._mtx.unlock();
//
//	// 走到这说明当前的SpanList中没有非空的span
//	// 从page cache获取k页的span
//	size_t k = SizeClass::NumMovePage(byte_size);
//
//	PageCache::GetInstance()->_pageMtx.lock();
//	Span* span = PageCache::GetInstance()->NewSpan(k);
//	PageCache::GetInstance()->_pageMtx.unlock();
//
//	// 将获取的span切成对应大小的内存对象 - 此时不需要加锁, 因为其他线程看不到这块span
//	// 计算大块内存的起始地址和大块内存的大小
//	char* start = (char*)(span->_pageId << PAGE_SHIFT); // 大块内存的起始地址
//	size_t bytes = span->_n << PAGE_SHIFT; // 大块内存的大小 - 字节数
//	char* end = start + bytes; // 大块内存的结束地址
//
//	// 把大块内存切成自由链表链接起来
//	// 先切一块做头, 方便尾插
//	span->_freeList = start;
//	void* tail = span->_freeList;
//	start += byte_size;
//	while (start < end)
//	{
//		NextObj(tail) = start;
//		tail = start;
//		start += byte_size;
//	}
//
//	// 将切好的span挂起来, 并加锁
//	list._mtx.lock();
//	list.PushFront(span);
//
//	return span;
//}


// 从SpanList或者page cache获取一个非空的span
Span* CentralCache::GetOneSpan(SpanList& list, size_t byte_size)
{
	// 判断SpanList中有没有非空的span
	Span* it = list.Begin();
	while (it != list.End())
	{
		if (it->_freeList != nullptr)
		{
			return it;
		}
		else
		{
			it = it->_next;
		}
	}

	// 解掉桶锁, 是为了thread cache释放内存回来不会被锁住
	list._mtx.unlock();

	// 走到这说明SpanList没有非空的span
	// 需要从page cache中获取
	PageCache::GetInstance()->_pageMtx.lock();
	Span* span = PageCache::GetInstance()->NewSpan(SizeClass::NumMovePage(byte_size));
	PageCache::GetInstance()->_pageMtx.unlock();

	// 将获取的span切成对应大小的内存对象, 此时不需要加锁, 因为其他线程看不到这个span
	char* start = (char*)(span->_pageId << PAGE_SHIFT); // 大块内存的起始地址
	size_t bytes = span->_n << PAGE_SHIFT; // 大块内存的大小 - 字节数
	char* end = start + bytes; // 大块内存的结束地址

	// 先切一块做头, 方便尾插
	span->_freeList = start;
	void* tail = span->_freeList;
	start += byte_size;
	while (start < end)
	{
		NextObj(tail) = start;
		tail = start;
		start += byte_size;
	}

	// 将切好的span挂起来, 并加锁
	list.PushFront(span);
	list._mtx.lock();

	return span;
}


// 从中心缓存获取一定数量的内存对象给thread cache
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t byte_size)
{
	assert(byte_size <= MAX_SIZE);

	size_t index = SizeClass::Index(byte_size);

	_spanLists[index]._mtx.lock();

	// 获取一个非空的span
	Span* span = GetInstance()->GetOneSpan(_spanLists[index], byte_size);
	assert(span);
	assert(span->_freeList);

	// 获取batchNum个内存对象
	// 如果不够batchNum个, 有多少拿多少
	start = span->_freeList;
	end = start;
	size_t actualNum = 1;
	size_t i = 0;
	while (i < batchNum - 1 && NextObj(end) != nullptr)
	{
		end = NextObj(end);
		actualNum++;
		i++;
	}

	span->_freeList = NextObj(end);
	NextObj(end) = nullptr;

	_spanLists[index]._mtx.unlock();

	return actualNum;
}


#define _CRT_SECURE_NO_WARNINGS 1

#include"ObjectPool.h"
#include"PageCache.h"


//// 获取一个k页的span
//Span* PageCache::NewSpan(size_t k)
//{
//	assert(k > 0 && k < NPAGES);
//
//	// 先判断是否有k页的span
//	if (!_spanLists[k].Empty())
//	{
//		return _spanLists[k].PopFront();
//	}
//
//	// 如果没有k页的span, 遍历k+1到最后一个
//	for (size_t i = k + 1; i < NPAGES; i++)
//	{
//		if (!_spanLists[i].Empty())
//		{
//			Span* nSpan = _spanLists[i].PopFront();
//			Span* kSpan = new Span;
//
//			kSpan->_pageId = nSpan->_pageId;
//			kSpan->_n = k;
//
//			nSpan->_pageId += k;
//			nSpan->_n -= k;
//
//			_spanLists[nSpan->_n].PushFront(nSpan);
//
//			return kSpan;
//		}
//	}
//
//	// 走到这说明后面没有大页的span了
//	// 此时需要向系统堆申请一个128页的span
//	Span* bigSpan = new Span;
//	void* ptr = SystemAlloc(NPAGES - 1);
//
//	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
//	bigSpan->_n = NPAGES - 1;
//
//	_spanLists[bigSpan->_n].PushFront(bigSpan);
//
//	return NewSpan(k);
//}



PageCache PageCache::_sInst;


// 获取一个k页的span
Span* PageCache::NewSpan(size_t k)
{
	assert(k > 0 && k < NPAGES);

	// 判断是否有k页的span
	if (!_spanLists[k].Empty())
	{
		return _spanLists[k].PopFront();
	}

	// 遍历k+1到最后一个
	for (size_t i = k + 1; i < NPAGES - 1; i++)
	{
		if (!_spanLists[i].Empty())
		{
			Span* nSpan = _spanLists[k].PopFront();
			Span* kSpan = new Span;

			kSpan->_pageId = nSpan->_pageId;
			kSpan->_n = k;

			nSpan->_pageId -= k;
			nSpan->_n += k;

			_spanLists[nSpan->_n].PushFront(nSpan);

			return kSpan;
		}
	}

	// 走到这说明没有大页的span
	// 需要向系统堆申请128页的span
	Span* bigSpan = new Span;
	void* ptr = SystemAlloc(NPAGES - 1);

	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
	bigSpan->_n = NPAGES - 1;

	_spanLists[bigSpan->_n].PushFront(bigSpan);

	return NewSpan(k);
}

#define _CRT_SECURE_NO_WARNINGS 1


#include"PageCache.h"
#include"ObjectPool.h"


PageCache PageCache::_sInst;


// 获取一个K页的span
Span* PageCache::NewSpan(size_t k)
{
	assert(k > 0 && k < NPAGES);

	// 先检查第K个桶里面有没有span
	if (!_spanLists[k].Empty())
	{
		return _spanLists[k].PopFront();
	}

	// 如果第k个桶里没有, 再找第K+1到最后一个桶
	for (size_t i = k + 1; i < NPAGES; i++)
	{
		if (!_spanLists[i].Empty())
		{
			Span* nSpan = _spanLists[i].PopFront();
			Span* kSpan = new Span;

			// 在nSpan的头部切一个k页下来
			// k页被返回
			// nSpan被挂回去
			kSpan->_pageId = nSpan->_pageId;
			kSpan->_n = k;

			nSpan->_pageId += k;
			nSpan->_n -= k;

			_spanLists[nSpan->_n].PushFront(nSpan);

			return kSpan;
		}
	}

	// 走到这个位置就说明后面没有大页的span了
	// 此时就需要向系统堆申请128页的span
	Span* bigSpan = new Span;
	void* ptr = SystemAlloc(NPAGES - 1);
	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
	bigSpan->_n = NPAGES - 1;

	_spanLists[bigSpan->_n].PushFront(bigSpan);

	return NewSpan(k);
}

#define _CRT_SECURE_NO_WARNINGS 1

#include"CentralCache.h"
#include"PageCache.h"

CentralCache CentralCache::_sInst;


//// 从SpanList或者page cache获取一个非空的Span
//Span* CentralCache::GetOneSpan(SpanList& list, size_t byte_size)
//{
//	// 先查看当前的SpanList中是否还有未分配的span
//	Span* it = list.Begin();
//	while (it != list.end())
//	{
//		if (it->_freeList != nullptr)
//		{
//			return it;
//		}
//		else
//		{
//			it = it->_next;
//		}
//	}
//
//	// 先把central cache的桶锁解掉, 这样如果其他线程释放内存对象回来不会阻塞
//	list._mtx.unlock();
//
//	// 走到这说明当前的SpanList中没有未分配的span, 需要从page cache中获取
//	PageCache::GetInstance()->_pageMtx.lock();
//	Span* span = PageCache::GetInstance()->NewSpan(SizeClass::NumMovePage(byte_size));
//	PageCache::GetInstance()->_pageMtx.unlock();
//
//	// 对获取的span进行切分不需要加锁, 因为这会其他线程获取不到这个span
//
//	// 计算span大块内存的起始地址和大块内存的大小
//	char* start = (char*)(span->_pageId << PAGE_SHIFT); // 大块内存的起始地址
//	size_t bytes = span->_n << PAGE_SHIFT; // 大块内存的大小 - 字节数
//	char* end = start + bytes; // 大块内存的结束地址
//
//	// 把大块内存切成自由链表链接起来
//	// 1. 先切下来一块做头, 方便尾插 - 提高命中率
//	span->_freeList = start;
//	start += byte_size;
//	void* tail = span->_freeList;
//	int i = 1;
//	while (start < end)
//	{
//		++i;
//		NextObj(tail) = start;
//		tail = NextObj(tail); // tail = start;
//		start += byte_size;
//	}
//
//	// 切好span以后，需要把span挂到桶里面去的时候，再加锁
//	list._mtx.lock();
//	list.PushFront(span);
//
//	return span;
//}


// 从SpanList或者page cache获取一个非空的span
Span* CentralCache::GetOneSpan(SpanList& list, size_t byte_size)
{
	// 先查看当前的SpanList中是否还有未分配的span
	Span* it = list.Begin();
	while (it != list.end())
	{
		if (it->_freeList != nullptr)
		{
			return it;
		}
		else
		{
			it = it->_next;
		}
	}

	// 先把central cache的桶锁解掉, 这样如果其他线程释放内存回来不会被阻塞
	list._mtx.unlock();


	// 走到这里说明当前的SpanList中没有未分配的span, 需要从page cache中获取
	PageCache::GetInstance()->_pageMtx.lock();
	Span* span = PageCache::GetInstance()->NewSpan(SizeClass::NumMovePage(byte_size));
	PageCache::GetInstance()->_pageMtx.unlock();

	// 对获取的span进行切分不需要加锁, 因为这会其他线程获取不到这个span

	// 计算span大块内存的起始地址和大块内存的大小
	char* start = (char*)(span->_pageId << PAGE_SHIFT); // 大块内存的起始地址
	size_t bytes = span->_n << PAGE_SHIFT; // 大块内存的大小 - 字节数
	char* end = start + bytes; // 大块内存的结束地址

	// 把大块内存切成自由链表链接起来
	// 先切下一块做头, 方便尾插 - 提高效率
	span->_freeList = start;
	start += byte_size;
	void* tail = span->_freeList;
	size_t i = 1;
	while (start < end)
	{
		NextObj(tail) = start;
		tail = start;
		start += byte_size;
		i++; // 这个i有什么用呢?
	}

	// 切好span以后, 需要将span挂到桶里面去, 再加锁
	list._mtx.lock();
	list.PushFront(span);

	return span;
}



// 从中心缓存获取一定数量的对象给thread cache
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t byte_size)
{
	size_t index = SizeClass::Index(byte_size);

	_spanLists[index]._mtx.lock();

	Span* span = GetOneSpan(_spanLists[index], byte_size);
	assert(span);
	assert(span->_freeList);

	// 从span中获取batchNum个内存对象
	// 如果不够batchNum个, 有多少拿多少
	start = span->_freeList;
	end = start;
	size_t i = 0;
	size_t actualNum = 1;
	while (i < batchNum - 1 && NextObj(end) != nullptr)
	{
		end = NextObj(end);
		i++;
		actualNum++;
	}
	span->_freeList = NextObj(end);
	NextObj(end) = nullptr; // 这个操作什么意思   取出的一段链表的表尾置空

	_spanLists[index]._mtx.unlock();

	return actualNum;
}

#pragma once


#include<iostream>
#include<cassert>
#include<mutex>
#include<algorithm>
using std::cout;
using std::endl;


static const size_t MAX_BYTES = 256 * 1024;
static const size_t NFREELISTS = 208;
static const size_t NPAGES = 129;
static const size_t PAGE_SHIFT = 13;


// 获取内存对象的头4/8字节的值, 即链接的下一个内存块的地址
inline void*& NextObj(void* obj)
{
	return (*(void**)obj);
}


// 管理切好的小块内存对象的自由链表
class FreeList
{
public:
	void PushRange(void* start, void* end)
	{
		assert(start);
		assert(end);

		NextObj(end) = _freeList;
		_freeList = start;
	}

	// 头插
	void Push(void* obj)
	{
		assert(obj);

		NextObj(obj) = _freeList;
		_freeList = obj;
	}

	// 头删
	void* Pop()
	{
		assert(_freeList);

		void* obj = _freeList;
		_freeList = NextObj(_freeList);

		return obj;
	}

	// 判空
	bool Empty()
	{
		return _freeList == nullptr;
	}

	size_t& MaxSize()
	{
		return _maxSize;
	}

private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;
};



// 对齐和映射规则
class SizeClass
{

public:
	// 整体控制在最多10%左右的内碎片浪费
	// [1, 128]                          8byte对齐                          freeList[0, 16)
	// [128+1, 1024]                     16byte对齐                         freeList[16, 72)
	// [1024+1, 8*1024]                  128byte对齐                        freeList[72, 128)
	// [8*1024+1, 64*1024]               1024byte对齐                       freeList[128, 184)
	// [64*1024+1, 256*1024]             8*1024byte对齐                     freeList[184, 208)


	// 对齐大小的计算 - 对齐后给的字节数
	/*static inline size_t _RoundUp(size_t size, size_t alignNum)
	{
		size_t alignSize = 0;
		if (size % alignNum != 0)
		{
			alignSize = (size / alignNum + 1) * alignNum;
		}
		else
		{
			alignSize = size;
		}

		return alignSize;
	}*/

	static inline size_t _RoundUp(size_t size, size_t alignNum)
	{
		return ((size + alignNum - 1) & ~(alignNum - 1));
	}

	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			assert(false);
		}
		return -1;
	}


	//计算映射到哪一个自由链表桶
	/*static inline size_t _Index(size_t bytes, size_t alignNum)
	{
		if (bytes % alignNum == 0)
		{
			return bytes / alignNum - 1;
		}
		else
		{
			return bytes / alignNum;
		}
	}*/

	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
	}

	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);

		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };// 前四个区间桶的数量

		if (bytes <= 128)
		{
			// return _Index(bytes, 8);
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			// return _Index(bytes, 16) + group_array[0];
			return _Index(bytes, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024)
		{
			// return _Index(bytes, 128) + group_array[0] + group_array[1];
			return _Index(bytes, 7) + group_array[0] + group_array[1];
		}
		else if (bytes <= 64 * 1024)
		{
			// return _Index(bytes, 1024) + group_array[0] + group_array[1] + group_array[2];
			return _Index(bytes, 10) + group_array[0] + group_array[1] + group_array[2];
		}
		else if (bytes <= 256 * 1024)
		{
			// return _Index(bytes, 8 * 1024) + group_array[0] + group_array[1] + group_array[2] + group_array[3];
			return _Index(bytes, 13) + group_array[0] + group_array[1] + group_array[2] + group_array[3];
		}
		else
		{
			assert(false);
		}
		return -1;
	}

	// 一次向central cache获取到的内存对象数量
	static size_t NumMoveSize(size_t size)
	{
		assert(size <= MAX_BYTES);

		size_t num = MAX_BYTES / size;

		if (num < 2)
			num = 2;

		if (num > 512)
			num = 512;

		return num;
	}

	// 一次向page cache要多少页
	static size_t NumMovePage(size_t size)
	{
		assert(size <= MAX_BYTES);

		size_t num = NumMoveSize(size);
		size_t npage = num * size;

		npage >>= PAGE_SHIFT;

		if (npage == 0)
			npage = 1;

		return npage;
	}

};

#ifdef _WIN64
	typedef unsigned long long PAGE_ID;
#elif _WIN32
	typedef size_t PAGE_ID;
#endif


// 管理以页为单位的大块内存
struct Span
{
	PAGE_ID _pageId = 0; // 大块内存起始页的页号
	size_t _n = 0; // 页数

	Span* _prev = nullptr; // 双向链表结构
	Span* _next = nullptr;

	void* _freeList = nullptr; // 自由链表
};


// 双向链表结构
class SpanList
{
public:
	SpanList()
	{
		_head = new Span;
		_head->_prev = _head;
		_head->_next = _head;
	}

	void PushFront(Span* newSpan)
	{
		assert(newSpan);

		Insert(Begin(), newSpan);
	}

	Span* PopFront()
	{
		assert(_head->_next != _head);

		Span* span = Begin();
		Erase(Begin());

		return span;
	}

	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		//prev newSpan pos
		prev->_next = newSpan;
		newSpan->_prev = prev;

		newSpan->_next = pos;
		pos->_prev = newSpan;
	}

	void Erase(Span* pos)
	{
		assert(pos);

		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

private:
	Span* _head = nullptr;

public:
	std::mutex _mtx;
};


#define _CRT_SECURE_NO_WARNINGS 1


#include"ThreadCache.h"
#include"CentralCache.h"


// 申请内存对象
void* ThreadCache::Allocate(size_t size)
{
	assert(size <= MAX_BYTES);

	size_t index = SizeClass::Index(size);
	size_t alignSize = SizeClass::RoundUp(size);

	if (!_freeLists[index].Empty())
	{
		return _freeLists[index].Pop();
	}
	else
	{
		return FetchFromCentralCache(index, alignSize);
	}
}


// 从central cache中获取内存对象
void* ThreadCache::FetchFromCentralCache(size_t index, size_t size)
{
	// 慢开始反馈调节算法
	// 1. 最开始不会一次向central cache要太多, 可能用不完浪费
	// 2. 如果不断有size大小的内存需求, 那么batchNum就会不断变大, 直至上限
	// 3. size越小, 一次获取到的内存对象就越多
	// 4. size越大, 一次获取到的内存对象就越少
	size_t batchNum = std::min(_freeLists[index].MaxSize(), SizeClass::NumMoveSize(size));
	if (batchNum == _freeLists[index].MaxSize())
	{
		_freeLists[index].MaxSize() += 1;
	}

	void* start = nullptr;
	void* end = nullptr;
	size_t actualNum = CentralCache::GetInstance()->FetchRangeObj(start, end, batchNum, size);
	assert(actualNum > 0);

	if (actualNum == 1)
	{
		assert(start == end);
		return start;
	}
	else
	{
		_freeLists[index].PushRange(NextObj(start), end);
		return start;
	}
}

#define _CRT_SECURE_NO_WARNINGS 1


#include"CentralCache.h"
#include"PageCache.h"


CentralCache CentralCache::_sInst;


// 从SpanList或者page cache获取一个非空的span
Span* CentralCache::GetOneSpan(SpanList& list, size_t size)
{
	// 判断当前的SpanList中是否有非空的span
	Span* it = list.Begin();
	while (it != list.End())
	{
		if (it->_freeList != nullptr)
		{
			return it;
		}
		else
		{
			it = it->_next;
		}
	}

	// 走到这说明需要从page cache中获取一个非空的span

	// 解除桶锁, 为了thread cache释放内存回来方便
	list._mtx.unlock();

	PageCache::GetInstance()->_pageMtx.lock();
	Span* span = PageCache::GetInstance()->NewSpan(SizeClass::NumMovePage(size));
	PageCache::GetInstance()->_pageMtx.unlock();

	char* start = (char*)(span->_pageId << PAGE_SHIFT);// 大块内存的起始地址
	size_t bytes = span->_n << PAGE_SHIFT;// 大块内存的大小 - 字节数
	char* end = start + bytes; // 大块内存的结束地址

	// 将大块内存切成自由链表链接起来
	// 先切一块做头, 方便尾插
	span->_freeList = start;
	void* tail = span->_freeList;
	start += size;
	while (start < end)
	{
		NextObj(tail) = start;
		tail = start;
		start += size;
	}

	list.PushFront(span);
	list._mtx.lock();

	return span;

}

// 从central cache获取一定数量的内存对象
size_t CentralCache::FetchRangeObj(void*& start, void*& end, size_t batchNum, size_t size)
{
	size_t index = SizeClass::Index(size);

	_spanLists[index]._mtx.lock();

	Span* span = GetOneSpan(_spanLists[index], size);
	assert(span);
	assert(span->_freeList);

	start = span->_freeList;
	end = start;
	size_t actualNum = 1;
	size_t i = 0;
	while (i < batchNum - 1 && NextObj(end) != nullptr)
	{
		end = NextObj(end);
		i++;
		actualNum++;
	}
	span->_freeList = NextObj(end); // 更新自由链表的指向
	NextObj(end) = nullptr; // 取出的一段内存对象的尾置空
	
	_spanLists[index]._mtx.unlock();

	return actualNum;
}

#define _CRT_SECURE_NO_WARNINGS 1

#include"PageCache.h"
#include"ObjectPool.h"


PageCache PageCache::_sInst;


// 获取一个K页的span
Span* PageCache::NewSpan(size_t k)
{
	assert(k > 0 && k < NPAGES);

	// 判断是否有k页的span
	if (!_spanLists[k].Empty())
	{
		return _spanLists[k].PopFront();
	}

	// 遍历k+1到最后
	for (size_t i = k + 1; i < NPAGES; i++)
	{
		if (!_spanLists[i].Empty())
		{
			Span* nSpan = _spanLists[i].PopFront();
			Span* kSpan = new Span;

			kSpan->_pageId = nSpan->_pageId;
			kSpan->_n = k;

			nSpan->_pageId += k;
			nSpan->_n -= k;

			_spanLists[nSpan->_n].PushFront(nSpan);

			return kSpan;
		}
	}

	// 从系统堆中申请一个128页的span
	Span* bigSpan = new Span;
	void* ptr = SystemAlloc(NPAGES - 1);
	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
	bigSpan->_n = NPAGES - 1;
	_spanLists[bigSpan->_n].PushFront(bigSpan);

	return NewSpan(k);
}


// 释放内存
void ThreadCache::Deallocate(void* ptr, size_t size)
{
	assert(ptr);
	assert(size <= MAX_BYTES);

	// 找到对应的自由链表桶, 将对象插入进去
	size_t index = SizeClass::Index(size);
	_freeLists[index].Push(ptr);

	// 当链表长度大于一次批量申请的内存时就开始还一段list给central cache
	if (_freeLists[index].Size() >= _freeLists[index].MaxSize())
	{
		ListTooLong(_freeLists[index], size);
	}
	
}


// 释放对象链表过长时, 回收内存对象到central cache
void ThreadCache::ListTooLong(FreeList& list, size_t size)
{
	void* start = nullptr;
	void* end = nullptr;
	list.PopRange(start, end, list.MaxSize());

	// 将一定数量的内存对象释放到span跨度
	CentralCache::GetInstance()->ReleaseListToSpans(start, size);
}



// 将一定数量的内存对象释放到span跨度
void CentralCache::ReleaseListToSpans(void* start, size_t size)
{
	size_t index = SizeClass::Index(size);

	_spanLists[index]._mtx.lock();

	while (start)
	{
		void* next = NextObj(start);

		// 获取从内存对象到span的映射
		Span* span = PageCache::GetInstance()->MapObjectToSpan(start);
		
		// 将start内存对象插入到该span的自由链表中
		NextObj(start) = span->_freeList;
		span->_freeList = start;
		span->_useCount--;

		// 说明span所有切分出去的内存对象都回来了
		// 这个span就可以回收给page cache, page cache可以再尝试去做前后页的合并
		if (span->_useCount == 0)
		{
			_spanLists[index].Erase(span);
			span->_freeList = nullptr;
			span->_prev = nullptr;
			span->_next = nullptr;

			// 释放span给page cache时, 使用page cache锁就可以了
			// 这时把桶锁解掉
			_spanLists[index]._mtx.unlock();

			// 释放空闲的span到page cache, 并合并相邻的span
			PageCache::GetInstance()->_pageMtx.lock();
			PageCache::GetInstance()->ReleaseSpanToPageCache(span);
			PageCache::GetInstance()->_pageMtx.unlock();

			_spanLists[index]._mtx.lock();
		}

		start = next;
	}

	_spanLists[index]._mtx.unlock();
}


// 获取从内存对象到span的映射
Span* PageCache::MapObjectToSpan(void* obj)
{
	assert(obj);

	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
	auto ret = _idSpanMap.find(id);

	if (ret != _idSpanMap.end())
	{
		return ret->second;
	}
	else
	{
		assert(false);
		return nullptr;
	}
}


// 释放空闲的span回到page cache, 并合并相邻的span
void PageCache::ReleaseSpanToPageCache(Span* span)
{
	// 尝试对span的前后页进行合并, 缓解内存碎片的问题

	// 向前合并
	while(1)
	{
		PAGE_ID prevId = span->_pageId - 1;
		auto ret = _idSpanMap.find(prevId);
		// 前面的页没有, 不合并了
		if (ret == _idSpanMap.end())
		{
			break;
		}

		// 前面相邻页的span在使用, 不合并了
		Span* prevSpan = ret->second;
		if (prevSpan->_isUse == true)
		{
			break;
		}

		// 合并出超过128页的span没办法管理, 不合并了
		if (prevSpan->_n + span->_n > NPAGES - 1)
		{
			break;
		}

		span->_pageId = prevSpan->_pageId;
		span->_n += prevSpan->_n;

		_spanLists[prevSpan->_n].Erase(prevSpan);

		delete prevSpan;
	}

	// 向后合并
	while (1)
	{
		PAGE_ID nextId = span->_pageId + span->_n;
		auto ret = _idSpanMap.find(nextId);
		// 后面的页不存在, 不合并了
		if (ret == _idSpanMap.end())
		{
			break;
		}

		// 后面相邻页的span在使用, 不合并了
		Span* nextSpan = ret->second;
		if (nextSpan->_isUse == true)
		{
			break;
		}

		//合并出超过128页的span没办法管理, 不合并了
		if (nextSpan->_n + span->_n > NPAGES - 1)
		{
			break;
		}

		span->_n += nextSpan->_n;
		_spanLists[nextSpan->_n].Erase(nextSpan);

		delete nextSpan;
	}

	_spanLists[span->_n].PushFront(span);
	span->_isUse = false;
	_idSpanMap[span->_pageId] = span; // 大块内存起始页的页号
	_idSpanMap[span->_pageId + span->_n - 1] = span; // 大块内存结束页的页号
}


#define _CRT_SECURE_NO_WARNINGS 1


#include"PageCache.h"
#include"ObjectPool.h"


PageCache PageCache::_sInst;


// 获取一个k页的span
Span* PageCache::NewSpan(size_t k)
{
	assert(k > 0 && k < NPAGES);

	if (!_spanLists[k].Empty())
	{
		return _spanLists[k].PopFront();
	}

	for (size_t i = k + 1; i < NPAGES; i++)
	{
		if (!_spanLists[i].Empty())
		{
			Span* kSpan = new Span;
			Span* nSpan = _spanLists[i].PopFront();

			kSpan->_pageId = nSpan->_pageId;
			kSpan->_n = k;

			nSpan->_pageId += k;
			nSpan->_n -= k;

			_spanLists[nSpan->_n].PushFront(nSpan);

			_idSpanMap[nSpan->_pageId] = nSpan;
			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

			for (size_t i = 0; i < kSpan->_n; i++)
			{
				_idSpanMap[kSpan->_pageId + i] = kSpan;
			}


			return kSpan;
		}
	}

	// 走到这说明需要从page cache中获取128页的span
	Span* bigSpan = new Span;
	void* ptr = SystemAlloc(NPAGES - 1);
	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
	bigSpan->_n = NPAGES - 1;

	_spanLists[bigSpan->_n].PushFront(bigSpan);

	return NewSpan(k);
}


// 获取内存对象到span的映射
Span* PageCache::MapObjectToSpan(void* obj)
{
	assert(obj);

	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;
	auto ret = _idSpanMap.find(id);
	if (ret != _idSpanMap.end())
	{
		return ret->second;
	}
	else
	{
		assert(false);
		return nullptr;
	}
}


// 释放空闲的span, 并合并前后页的span
void PageCache::ReleaseSpanToPageCache(Span* span)
{
	assert(span);

	// 尝试合并前后页的span, 缓解内存碎片的问题

	// 向前合并
	while (1)
	{
		PAGE_ID prevId = span->_pageId - 1;

		auto ret = _idSpanMap.find(prevId);
		// 没有前一页的span, 不合并了
		if (ret == _idSpanMap.end())
		{
			break;
		}

		// 前一页的span被使用了, 不合并了
		Span* prevSpan = ret->second;
		if (prevSpan->_isUse == true)
		{
			break;
		}

		// 合并出大于128页的span没办法管理, 不合并了
		if (span->_n + prevSpan->_n > NPAGES - 1)
		{
			break;
		}

		span->_pageId = prevSpan->_pageId;
		span->_n += prevSpan->_n;

		_spanLists[prevSpan->_n].Erase(prevSpan);
		delete prevSpan;
	}

	// 向后合并
	while (1)
	{
		PAGE_ID nextId = span->_pageId + span->_n;

		auto ret = _idSpanMap.find(nextId);
		if (ret == _idSpanMap.end())
		{
			break;
		}

		Span* nextSpan = ret->second;
		if (nextSpan->_isUse == true)
		{
			break;
		}

		if (span->_n + nextSpan->_n > NPAGES - 1)
		{
			break;
		}

		span->_n += nextSpan->_n;

		_spanLists[nextSpan->_n].Erase(nextSpan);
		delete nextSpan;
	}

	_spanLists[span->_n].PushFront(span);
	span->_isUse = false;

	_idSpanMap[span->_pageId] = span;
	_idSpanMap[span->_pageId - 1] = span;
}

#define _CRT_SECURE_NO_WARNINGS 1


#include"PageCache.h"
#include"ObjectPool.h"


PageCache PageCache::_sInst;


// 获取一个k页的span
Span* PageCache::NewSpan(size_t k)
{
	assert(k > 0 && k < NPAGES);

	if (!_spanLists[k].Empty())
	{
		Span* kSpan = _spanLists[k].PopFront();

		// 建立页号到span的映射
		for (size_t i = 0; i < kSpan->_n; i++)
		{
			_idSpanMap[i] = kSpan;
		}
	}

	for (size_t i = k + 1; i < NPAGES; i++)
	{
		if (!_spanLists[i].Empty())
		{
			Span* kSpan = new Span;
			Span* nSpan = _spanLists[i].PopFront();

			kSpan->_pageId = nSpan->_pageId;
			kSpan->_n = k;

			nSpan->_pageId += k;
			nSpan->_n -= k;

			_spanLists[nSpan->_n].PushFront(nSpan);

			// 挂到page cache中的span要记住其起始页号和终止页号
			_idSpanMap[nSpan->_pageId] = nSpan;
			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

			// 建立页号到span的映射
			for (size_t i = 0; i < kSpan->_n; i++)
			{
				_idSpanMap[i] = kSpan;
			}

			return kSpan;
		}
	}

	// 走到这说明需要从系统堆中申请128页span
	Span* bigSpan = new Span;
	void* ptr = SystemAlloc(NPAGES - 1);
	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
	bigSpan->_n = NPAGES - 1;

	_spanLists[bigSpan->_n].PushFront(bigSpan);

	return NewSpan(k);
}


// 获取从内存对象到span的映射
Span* PageCache::MapObjectToSpan(void* obj)
{
	assert(obj);

	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;

	auto ret = _idSpanMap.find(id);
	if (ret != _idSpanMap.end())
	{
		return ret->second;
	}
	else
	{
		assert(false);
		return nullptr;
	}
}


// 释放空闲的span, 并尝试合并前后页的span
void PageCache::ReleaseSpanToPageCache(Span* span)
{
	assert(span);

	// 尝试做前后页span的合并, 缓解内存碎片的问题

	// 先前合并
	while (1)
	{
		PAGE_ID prevId = span->_pageId - 1; // 前一页span的终止页号

		// 1. 不存在前一页的span, 不合并了
		auto ret = _idSpanMap.find(prevId);
		if (ret == _idSpanMap.end())
		{
			break;
		}

		// 2. 前一页的span被使用了, 不合并了
		Span* prevSpan = ret->second;
		if (prevSpan->_isUse == true)
		{
			break;
		}

		// 3. 合并出比128页大的span, 不合并了
		if (span->_n + prevSpan->_n > NPAGES - 1)
		{
			break;
		}

		span->_pageId = prevSpan->_pageId;
		span->_n += prevSpan->_n;

		_spanLists[prevSpan->_n].Erase(prevSpan);
		delete prevSpan;
	}

	// 向后合并
	while (1)
	{
		PAGE_ID nextId = span->_pageId + span->_n; // 后一页span的起始页号

		// 1.不存在后一页的span, 不合并了
		auto ret = _idSpanMap.find(nextId);
		if (ret == _idSpanMap.end())
		{
			break;
		}

		// 2. 后一页的span被使用了, 不合并了
		Span* nextSpan = ret->second;
		if (nextSpan->_isUse == true)
		{
			break;
		}

		// 3.合并出比128页的span没办法管理, 不合并了
		if (span->_n + nextSpan->_n > NPAGES - 1)
		{
			break;
		}

		span->_n += nextSpan->_n;

		_spanLists[nextSpan->_n].Erase(nextSpan);
		delete nextSpan;
	}

	// 将合并后的span挂到page cache中, 并建立前后页到span的映射, 方便后面合并出更大的span
	_spanLists[span->_n].PushFront(span);
	span->_isUse = false;

	_idSpanMap[span->_pageId] = span;
	_idSpanMap[span->_pageId + span->_n - 1] = span;
}

		return _spanLists[k].PopFront();
#define _CRT_SECURE_NO_WARNINGS 1


#include"PageCache.h"
#include"ObjectPool.h"


PageCache PageCache::_sInst;


// 获取一个k页的span
Span* PageCache::NewSpan(size_t k)
{
	assert(k > 0 && k < NPAGES);

	if (!_spanLists[k].Empty())
	{
		Span* kSpan = _spanLists[k].PopFront();

		// 建立页号到span的映射
		for (size_t i = 0; i < kSpan->_n; i++)
		{
			_idSpanMap[kSpan->_pageId + i] = kSpan;
		}
	}

	for (size_t i = k + 1; i < NPAGES; i++)
	{
		if (!_spanLists[i].Empty())
		{
			Span* kSpan = new Span;
			Span* nSpan = _spanLists[i].PopFront();

			kSpan->_pageId = nSpan->_pageId;
			kSpan->_n = k;

			nSpan->_pageId += k;
			nSpan->_n -= k;

			_spanLists[nSpan->_n].PushFront(nSpan);

			// 挂到page cache中的span要建立起始和终止页号与span的映射
			_idSpanMap[nSpan->_pageId] = nSpan;
			_idSpanMap[nSpan->_pageId + nSpan->_n - 1] = nSpan;

			// 分配给central cache使用的span要每一页都要建立页号到span的映射
			for (size_t i = 0; i < kSpan->_n; i++)
			{
				_idSpanMap[kSpan->_pageId + i] = kSpan;
			}

			return kSpan;
		}
	}

	Span* bigSpan = new Span;
	void* ptr = SystemAlloc(NPAGES - 1);
	bigSpan->_pageId = (PAGE_ID)ptr >> PAGE_SHIFT;
	bigSpan->_n = NPAGES - 1;

	_spanLists[bigSpan->_n].PushFront(bigSpan);

	return NewSpan(k);
}


// 获取从页号到span的映射
Span* PageCache::MapPageToSpan(void* obj)
{
	assert(obj);

	PAGE_ID id = (PAGE_ID)obj >> PAGE_SHIFT;

	auto ret = _idSpanMap.find(id);
	if (ret != _idSpanMap.end())
	{
		return ret->second;
	}
	else
	{
		assert(false);
		return nullptr;
	}
}


// 释放空闲的span, 并尝试做前后页的span的合并
void PageCache::ReleaseSpanToPageCache(Span* span)
{
	assert(span);

	// 尝试做前后页的span的合并, 以达到缓解内存碎片的目的

	// 向前合并
	while (1)
	{
		PAGE_ID prevId = span->_pageId - 1; // 前一页的页号

		// 1. 不存在前一页的span, 不合并了
		auto ret = _idSpanMap.find(prevId);
		if (ret == _idSpanMap.end())
		{
			break;
		}

		// 2. 前一页的span被使用了, 不合并了
		Span* prevSpan = ret->second;
		if (prevSpan->_isUse == true)
		{
			break;
		}

		// 3. 合并出大于128页的span, 不合并了
		if (span->_n + prevSpan->_n > NPAGES - 1)
		{
			break;
		}

		span->_pageId = prevSpan->_pageId;
		span->_n += prevSpan->_n;

		_spanLists[prevSpan->_n].Erase(prevSpan);
		delete prevSpan;
	}

	// 向后合并
	while (1)
	{
		PAGE_ID nextId = span->_pageId + span->_n; // 后一页span的页号

		auto ret = _idSpanMap.find(nextId);
		if (ret == _idSpanMap.end())
		{
			break;
		}

		Span* nextSpan = ret->second;
		if (nextSpan->_isUse == true)
		{
			break;
		}

		if (span->_n + nextSpan->_n > NPAGES - 1)
		{
			break;
		}

		span->_n += nextSpan->_n;

		_spanLists[nextSpan->_n].Erase(nextSpan);
		delete nextSpan;
	}

	_spanLists[span->_n].PushFront(span);
	span->_isUse = false;

	_idSpanMap[span->_pageId] = span;
	_idSpanMap[span->_pageId + span->_n - 1] = span;
}